Дискретная математика: Основы подсчета

Подсчёт — это искусство определения размера конечных множеств без утомительной ручной пересчёта. Используя логические структуры, мы можем решать задачи от простых комбинаций меню до сложных криптографических перестановок.

Логика «ИЛИ» и «И»

Два основания поддерживают всю область комбинаторики. Их применение полностью зависит от того, рассматриваем ли мы задачу как один выбор из нескольких категорий или как последовательность выборов.

Принцип сложения (Правило суммы)

Если множество $X$ разбито на непересекающиеся подмножества $X_1, X_2, \dots, X_n$, то общее количество элементов $|X|$ равно сумме размеров этих подмножеств:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Аналогия: Выбор обеда в кафе «Kay’s Quick Lunch», выбирая либо бутерброд из меню основных блюд, либо закуску из меню закусок. Вы не можете выбрать оба одновременно — вы выбираете один пункт.

Принцип умножения (Правило произведения)

Если деятельность состоит из $t$ последовательных шагов, где на шаге $i$ есть $n_i$ возможных исходов, то общее количество способов завершить задачу равно произведению вариантов на каждом шаге:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Аналогия: Конфигурирование грузовика «Big Pickup». Вам нужно выбрать двигатель (5 вариантов) И стиль кабины (3 варианта). Общее количество конфигураций равно $5 \times 3 = 15$.

Реализация в коде и сложность

В информатике эти принципы проявляются в структурах циклов. Последовательные циклы представляют принцип сложения, а вложенные циклы — принцип умножения.

// Принцип сложения (m + n выполнений)

for i = 1 to m: println(i)

for j = 1 to n: println(j)

// Принцип умножения (m * n выполнений)

for i = 1 to m:

for j = 1 to n:

println(i, j)

🎯 Основной принцип

Различайте по ключевым словам: «ИЛИ» означает сложение (взаимоисключающие выборы), а «И» или «последовательный» — умножение (независимые шаги в последовательности).

ВОПРОС 1

Сколько обедов в кафе «Kay’s Quick Lunch» (Рисунок 6.1.1) состоят из одной закуски и одного напитка, если есть 3 закуски и 4 напитка?

ВОПРОС 2

В приведённом фрагменте кода сколько раз выполняются операции вывода в общей сложности? [Код: for i = 1 to m, println(i), for j = 1 to n, println(j)]

m × n

$m + n$

$m^n$

$n^m$

ВОПРОС 3

Сколько строк длины 3 можно составить из букв {A, B, C, D, E}, если разрешены повторения?

125

243

ВОПРОС 4

Пользуясь публичным ключом (n=713, e=29), каково шифрование сообщения $M = 333$?

333

557

128

712

ВОПРОС 5

Сколько строк длины 3 из букв {A, B, C, D, E} содержат хотя бы одну букву А (повторения разрешены)?

125

Вызов: Расширенное комбинаторное рассуждение

Грузовики, треугольники и ящики

Сценарий: Большие грузовики привлекают тем, что их можно настраивать почти бесконечным числом способов. Статья из «Нью-Йорк Таймс» говорит, что для подсчёта всех конфигураций нужны математические навыки, как у Уилла Хантинга. Давайте проанализируем модель с 5 вариантами двигателей (3,9 л V6, 5,2 л V8, 5,9 л V8, 5,9 л турбодизель, 8 л V10).

В1

Определите лексикографический порядок и объясните, почему он полезен при подсчёте структур.

Решение: Лексикографический порядок — это обобщение алфавитного порядка слов в словаре на последовательности упорядоченных символов. Если две последовательности $a_1...a_n$ и $b_1...b_n$, то $a < b$, если на первом индексе $i$, где $a_i \neq b_i$, выполняется $a_i < b_i$. Он полезен, потому что обеспечивает систематический способ перечисления всех перестановок или сочетаний без пропусков или повторений.

В2

Что такое перестановка элементов $x_1, \dots, x_n$? Приведите формальное определение.

Решение: Перестановка множества различных объектов — это упорядоченная расстановка этих объектов. Для множества из $n$ элементов перестановка — это биекция из множества $\{1, 2, \dots, n\}$ в само себя, где важен порядок элементов в итоговой последовательности.

В3

Докажите, что если из обычной колоды из 52 карт выбраны пять карт, то по крайней мере две из них одного масти.

Решение: Это применение принципа ящиков. Есть 4 возможные масти («ящики»), и выбираются 5 карт («голуби»). Поскольку $5 > 4$, по принципу ящиков, по крайней мере одна масть должна содержать $\lceil 5/4 \rceil = 2$ карты. Следовательно, по крайней мере две карты должны быть одной масти.

В4

Сколькими способами можно выбрать восемь шаров из мешка, содержащего красные, синие и жёлтые шары (по крайней мере по 8 каждого цвета)? (Сложность: корневые слова: 18, длина: короткая)

Решение: Это задача на сочетания с повторениями. Используем формулу звёзд и полос: $C(n + r - 1, r)$, где $n = 3$ категории, $r = 8$ выборов: $C(3 + 8 - 1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ способов.